package com.shuang.tree32;

import java.util.HashMap;
import java.util.Map;

public class BuildTree {
    //递归实现 先从后序数组找到最后一个元素（肯定是中节点） 然后用这个元素的值在中序数组中找到其索引位置
    // 对中序数组进行切割 得到的左右两部分是左右子树  又根据左右子树元素个数肯定相同 所以可以根据左子树的元素个数
    // 切割后序数组 也将其分成左右子树 再取最后一个元素 重复过程
    Map<Integer, Integer> map; //将中序数组中元素值和索引位置存起来 便于根据后序元素值查找中序数组中元素索引位置

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        //先判断 数组为空时 直接返回空即可
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }

        //将map中存好值
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        //采取索引左闭右开的原则
        TreeNode root = findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
        return root;
    }

    //递归 构建树 索引左闭右开原则
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是左闭右开
        if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }

        //根据后续数组最后的元素 找到在中序数组该元素位置
        //后序数组最后一个元素值
        int rootValue = postorder[postEnd - 1];
        //该元素在中序数组中的索引位置
        int index = map.get(rootValue);

        //并根据该元素构建节点（中节点）
        TreeNode root = new TreeNode(rootValue);

        //拿到中序数组左子树元素个数 根据左子树个数 切割后续数组
        int leftNum = index - inBegin;

        //根据索引下标直接切割中序数组和后序数组(坚持左闭右开原则) 分成左右子树 对切割好的数组 左子树和右子树进行递归
        //左子树 ：中序数组索引 从开始到索引位置[) 后序从开始到左子树元素个数位置保证数组左区域个数一致
        root.left = findNode(inorder, inBegin, index, postorder, postBegin, postBegin + leftNum);
        root.right = findNode(inorder, index + 1, inEnd, postorder, postBegin + leftNum, postEnd - 1);

        return root;

    }
}
